Singleton arc consistency is an important type of local consistency which hasbeen recently shown to solve all constraint satisfaction problems (CSPs) overconstraint languages of bounded width. We aim to characterise all classes ofCSPs defined by a forbidden pattern that are solved by singleton arcconsistency and closed under removing constraints. We identify five newpatterns whose absence ensures solvability by singleton arc consistency, fourof which are provably maximal and three of which generalise 2-SAT. Combinedwith simple counter-examples for other patterns, we make significant progresstowards a complete classification.
展开▼
